<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html><head>


  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  <meta http-equiv="Content-Language" content="es-ar">
  <meta name="GENERATOR" content="A mano con lo que venga">
  <meta name="Author" content="Nicolas Wolovick">
  <meta name="keywords" content="kernel modules fifo sistemas operativos FaMAF educacion education operating systems linux producer consumer productor consumidor">
  <style type="text/css">
	H1, H2, H3, DIV, P, LI,
	UL, OL, TABLE, TD, TR {font-family: lucida sans, helvetica, arial, sans-serif;}
	pre {background: #eee; border: 1px dashed #889; margin-left: 3em; padding: 1ex;}
	dt {font-family: monospace; font-weight: bold;}
  </style><title>Lab3: Productor-Consumidor en espacio de kernel</title></head><body>

<!--============================================================-->
<h1><a class="autolink" title="Lab3: Productor-Consumidor en espacio de Kernel" href="http://educa.di.unc.edu.ar/mod/forum/view.php?id=3226">Lab3: Productor-Consumidor en espacio de kernel</a></h1>

<h3>Julio Bianco, Edgardo Hames</h3>
<h4><a class="autolink" title="Enunciado" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3328">Enunciado</a>: Nicolás Wolovick</h4>

<!--============================================================-->
<h1>Objetivos</h1>
<ul>
	<li>Implementar un controlador de dispositivo de caracteres sencillo en espacio de kernel.</li>
	<li>Utilizar
el device driver y programas en espacio de usuario para revelar los
mecanismos internos de las bibliotecas estandar y el kernel.</li>
</ul>

<!--============================================================-->
<h1>Introducción</h1>

<p>
Se deberá leer el apunte <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/pcl.pdf">Programación de Controladores para Linux</a>.


<!---------------------------------------------------------------->
</p><h2>Ejemplo: los dispositivos <tt>hello</tt>, <tt>hello_param</tt> y <tt>nulo</tt></h2>

<p>
Damos tres <a class="autolink" title="Ejemplos" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3117">ejemplos</a> de módulos a fin de probarlos y mostrar la estructura básica.

<!--............................................................-->
</p><h3>Hola Mundo en espacio de kernel</h3>

<table cellspacing="10">
<tbody><tr valign="top">
<td>
<p>
El siguiente ejemplo imprime un "Hello, world" al cargar el módulo y un "Goodbye, cruel world" cuando se lo quita del sistema.
Solamente se define la inicialización y destrucción del módulo.
<br>
También se puede ver el uso de la funcion <tt>printk</tt> para imprimir mensajes informativos.
</p><pre width="50"><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/hello.c"><tt>hello.c</tt></a>
#include &lt;linux/init.h&gt;
#include &lt;linux/module.h&gt;

MODULE_LICENSE("GPL");

static int hello_init(void)
{
	printk(KERN_ALERT "Hello, world\n");
	return 0;
}

static void hello_exit(void)
{
	printk(KERN_ALERT "Goodbye, cruel world\n");
}

module_init(hello_init);
module_exit(hello_exit);
</pre>
</td>
<td>
<p>
El archivo Makefile es sencillo y bastante genérico por lo que servirá, adaptando los nombres, para el desarrollo del proyecto.
</p><pre width="75"><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/Makefile"><tt>Makefile</tt></a>
KERNELDIR ?= /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)

obj-m := hello.o
module-objs := hello.o

default:
	$(MAKE) -C $(KERNELDIR) M=$(PWD) modules

clean:
	rm -f $(OBJECTS) *.ko *.o *.mod.* *.symvers *~
</pre>
</td>
</tr>
</tbody></table>

<p>
Podemos insertarlo y removerlo del sistema y ver los efectos que produce.
</p><pre width="100">nicolasw@negra:~/sistop/trunk/TemasProgramacion/LinuxDrivers/src/hello$ sudo insmod ./hello.ko
nicolasw@negra:~/sistop/trunk/TemasProgramacion/LinuxDrivers/src/hello$ sudo rmmod hello
nicolasw@negra:~/sistop/trunk/TemasProgramacion/LinuxDrivers/src/hello$ dmesg | tail -2 
[ 3889.892180] Hello, world
[ 3892.863703] Goodbye, cruel world
</pre>
<p>
Una modificación nos permite <b>aceptar parámetros de entrada</b> para nuestro módulo.
</p><pre width="75"><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/hello_param.c"><tt>hello_param.c</tt></a>
#include &lt;linux/init.h&gt;
#include &lt;linux/module.h&gt;

MODULE_LICENSE("GPL");

static char *whom = "world";
static int howmany = 1;
module_param(howmany, int, S_IRUGO);
module_param(whom, charp, S_IRUGO);

static int hello_init(void)
{
	int i;
	for (i = 0; i &lt; howmany; i++){
		printk(KERN_ALERT "Hello, %s\n", whom);
	}
	return 0;
}

static void hello_exit(void)
{
	printk(KERN_ALERT "Goodbye, cruel %s\n", whom);
}

module_init(hello_init);
module_exit(hello_exit);
</pre>

<p>
Para pasarle los parámetros hacemos:
</p><pre width="50">insmod ./hello_param.ko howmany=8 whom=Myself
rmmod hello_param
</pre>

<p>
Y con <code>dmesg</code> miramos sus efectos:
</p><pre width="50">[ 3824.384669] Hello, Myself
[ 3824.384678] Hello, Myself
[ 3824.384681] Hello, Myself
[ 3824.384683] Hello, Myself
[ 3824.384686] Hello, Myself
[ 3824.384688] Hello, Myself
[ 3824.384691] Hello, Myself
[ 3824.384693] Hello, Myself
[ 3831.493057] Goodbye, cruel Myself
</pre>


<!--............................................................-->
<h3>Dispositivo nulo</h3>

<p>
El dispositivo <tt>nulo</tt> es igualmente inútil, pero implementa más funcionalidades.
<br>
Este ya es un <i>dispositivo de caracteres</i> que se registra (<tt>register_chrdev</tt>, <tt>unregister_chrdev</tt>), con su <i>major number</i>, para estar disponible a través de la interface del <i>filesystem</i> usualmente en <tt>/dev/</tt>.

</p><p>
Como el dispositivo está asociado a un dispositivo de caracteres, es posible leerlo y escribirlo.
<br>
Para tener esta funcionalidad el módulo define la estructura <code>file_operations</code> dentro del módulo <code><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/nuloops.h">nuloops.h</a>, <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/nuloops.c">nuloops.c</a></code>. 
</p><pre width="50">struct file_operations nulo_fops = {
	.owner	=	THIS_MODULE,
	.open	=	nulo_open,
	.read	=	nulo_read,
	.write	=	nulo_write,
	.release=	nulo_release
};
</pre>

<p>
Notar que en <tt>nulo</tt> todas las operaciones son <i>stubs</i> que no realizan ningún cambio en el sistema, pero imprimen información de debugging.
<br>
Por ejemplo veamos el <code>write</code>.
</p><pre width="100">static ssize_t nulo_write(struct file *fp, const char *buf, size_t count, loff_t *offset)
{
/**
 * Siempre se puede escribir en /dev/nulo y nunca nos quedaremos sin espacio.
 */
	dprintk("nulo: write %d.\n", count);
	return count;
}
</pre>

<p>
El código se completa con un módulo principal <code><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/main.c">main.c</a></code> donde se produce la inicialización y destrucción del módulo, asi como un pequeñísimo módulo de debugging <code><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/debug.h">debug.h</a></code>.

<!---------------------------------------------------------------->
</p><h2>Ejercicios</h2>
<ul>
	<li>Compilar y probar los dispositivos <tt>hola</tt>, <tt>hola_param</tt> y <tt>nulo</tt>.</li>
	<li>Modificar el código para imprimir un mensaje informativo cada vez que se llama a <tt>nulo_open</tt> y <tt>nulo_release</tt>, además de los ya establecidos para <tt>nulo_read</tt> y <tt>nulo_write</tt>.
		<br>Realizar diversas operaciones con el dispositivo (<tt>cat /dev/nulo</tt>, <tt>echo "cadena" &gt; /dev/nulo</tt>, etc.) y comprobar como se correlacionan con llamadas a estas funciones dentro del núcleo.
	</li>
	<li>Escribir un programa en espacio de usuario que abra el dispositivo <tt>open("/dev/nulo", O_RDONLY)</tt> y se duerma esperando <tt>sleep(1&gt;&gt;20)</tt>. Lanzar dos o más procesos corriendo este programa.
		<br>¿Cuántas veces se llamó a <tt>open</tt> y <tt>release</tt>? ¿Por qué?
	</li>
	<li>¿Los dispositivos tienen que estar necesariamente dentro de <tt>/dev/</tt>?</li>
	<li>¿Qué sucede si <tt>nulo_write</tt> retorna 0 en vez de la cantidad de bytes que se quieren escribir?</li>
</ul>


<!--============================================================-->
<h1>Tareas</h1>

<p>
El trabajo se divide en dos partes.
</p><ol>
	<li>Implementar una cola fifo como módulo de kernel.</li>
	<li>Utilizar esa implementación para observar el comportamiento de los mecanismos de buffering de la <code>libc</code>.</li>
</ol>

<!---------------------------------------------------------------->
<h2>1. El Productor Consumidor en espacio de kernel: <tt>/dev/fifo</tt></h2>

<p>
Se deberá implementar un dispositivo de caracteres en espacio de kernel
utilizando el mecanismo de módulos de Linux, que ofrezca un servicio de
IPC (inter-process communication) muy sencillo: el buffer acotado.
</p><p>
Teniendo la implementación de un <b>buffer acotado</b> en este caso denominado <code>rbuffer.{<a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/rbuffer.h">h</a>, <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/rbuffer.c">c</a>}</code>
(ring buffer), se tiene que completar la implementación para poder
utilizar este buffer como un espacio de comunicación entre procesos.
Cuando un proceso escriba en <tt>/dev/fifo</tt> los datos serán <b>encolados</b> en el <tt>rbuffer</tt> y cuando éste u otro proceso quiera leer, los datos necesarios serán <b>desencolados</b>.

</p><p>
La solución no es directa, hay que tener en cuenta dos problemas:
</p><ul>
	<li>El buffer es finito, luego si el buffer se llena, el
proceso que escribe debe ser puesto a dormir hasta que haya espacio
generado por un lector. Simétricamente para los lectores.</li>
	<li>Se deben copiar datos desde espacio de kernel a usuario en <tt>read</tt> y de usuario a kernel en <tt>write</tt>.</li>
</ul>

<p>
También se pide que el módulo tome dos <b>parámetros de entrada</b>:
</p><ul>
	<li><code>major</code>: major number al cual se enganchará el dispositivo.</li>
	<li><code>size</code>: que define el tamaño del buffer acotado.</li>
</ul>

Opcionalmente, se podrá agregar un tercer parámetro <code>debug</code>
booleano, que determine al momento de carga del módulo si deben
habilitarse las opciones de depuración. Así el comportamiento de la
macro <code>dprintk</code> no estará definido en tiempo de compilación, sino de enlace con el núcleo.

<!--............................................................-->
<h3>El <code>rbuffer</code>, la estructura compartida</h3>

<p>
Es una implentación estándar de una cola de tamaño acotado.
<br>
Dado un tamaño <i>n</i>, tenemos un arreglo de <i>n+1</i> posiciones y dos índices, <i>wpos</i> que apunta al valor que se escribirá (encolar) y <i>rpos</i> que apunta al valor que se leerá (desencolar).
<br>
El buffer está vacío cuando  <i>wpos=rpos+1 mod n</i> y lleno cuando <i>wpos=(rpos-1) mod n</i>.

</p><p>
Declarar variables de tipo ring buffer que contendrán los datos, se realiza de la siguiente manera:
</p><p>
</p><pre width="50">rbuffer_t device_queue;
</pre>

<p>
Para crear y destruir una instancia del TAD tenemos las funciones:
</p><ul>
	<li><tt>rbuffer_t rbuffer_create(const unsigned int size)</tt>
	</li><li><tt>void rbuffer_destroy(rbuffer_t buf)</tt>
</li></ul>

<p>
Las funciones proyectoras y modificadoras del ring buffer son:
</p><ul>
	<li><tt>bool rbuffer_is_empty(rbuffer_t buf)</tt>: indica si el buffer está vacío.
	</li><li><tt>bool rbuffer_is_full(rbuffer_t buf)</tt>: indica si el buffer está lleno.
	</li><li><tt>bool rbuffer_insert(rbuffer_t buf, const byte data)</tt>: encola un valor.
	</li><li><tt>bool rbuffer_remove(rbuffer_t buf, byte *data)</tt>: desencola un valor.
</li></ul>


<!--............................................................-->
<h3>Como atacar el problema</h3>

<p>
El apunte de <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-devfifo/pcl.pdf">Programación de Controladores para Linux</a> muestra todas las herramientas necesarias.

</p><p>
La implementación deberá ser <b>modular</b> siguiendo los principios de <b>ocultamiento</b> que se vieron en los laboratorios anteriores.
<br>
Se recomienda seguir los lineamientos propuestos en el documento CodingStyle que acompaña al código del núcleo de Linux.



<!--............................................................-->
</p><h3>Pruebas de corrección</h3>

<p>
Se proponen los siguentes testeos para comprobar que la implementación es correcta.
<br>
Sean <i>C0,C1</i> dos consolas de ejecución:

</p><ol>
	<li>Ver si transfiere un byte en cero:
		<br><i>C0</i>: <tt>dd if=/dev/zero bs=1 count=1 of=/dev/fifo</tt>
		<br><i>C1</i>: <tt>dd if=/dev/fifo | hexdump </tt>
	</li>
	<li>Ver si transfiere bien los 32 primeros MB de una película, en bloques de 1MB:
		<br><i>C0</i>: <tt>dd if=~/matrix.avi bs=1M count=32 | tee /dev/fifo | md5sum</tt>
		<br><i>C1</i>: <tt>dd if=/dev/fifo | md5sum</tt>
		<br>Las sumas de comprobación deben dar iguales.
	</li>
	<li>La prueba anterior pero con tamaños de bloque y totales que sean uno menos, igual y uno más del tamaño del buffer.</li>
	<li>Todas
las pruebas anteriores pero cambiando la implementación para que el
tamaños de buffer sea 1, 2, 3 bytes, 172 bytes y 257 bytes.</li>
</ol>


<!---------------------------------------------------------------->
<h2>2. Observación de los mecanismos de buffering de <tt>libc</tt></h2>
<table cellspacing="10">
<tbody><tr valign="top">
<td>
<p>
Gracias a <tt>/dev/fifo</tt> tenemos control sobre los dos extremos de toda la "pila" que compone un sistema operativo:
</p><ul>
	<li>Podemos escribir y/o usar cualquier programa en espacio de usuario que utilice el dispositivo.</li>
	<li>Podemos imprimir mensajes de información que muestren las llamadas al dispositivo en espacio de kernel.</li>
</ul>

<p>
Con esta idea simple, es posible <b>exponer</b> parte de la estructura interna de la <tt>libc</tt>, más concretamente sus mecanismos internos de buffering.

</p><p>
Se deberán <b>escribir dos programas</b>, uno sirve para mostar lo que hace la <tt>libc</tt> con paquetes de 
distintos tamaños y el otro para ver como esto afecta la velocidad de proceso.
</p></td>
<td>
<img src="lab-devfifo_archivos/osstack.png" alt="OS Stack">
</td>
</tr>
</tbody></table>

<!--............................................................-->
<h3>¿Cómo el tamaño afecta lo que el kernel recibe?</h3>

<p>
Realizar un programa que escriba en el <tt>/dev/fifo</tt> secuencias de datos de longitud de <i>L=1</i> hasta <i>H=65536</i> bytes, en incrementos de <i>S=100</i>.
<br>
Mirar el tamaño de las escrituras que llegan al dispositivo, explicar <b>que</b> fenómeno sucede y <b>porque</b>.

<!--............................................................-->
</p><h3>¿Cómo el tamaño afecta la performance?</h3>

<p>
Usando el programa anterior agregar una llamada a <tt><a href="http://www.hmug.org/man/3/fflush.php">fflush()</a></tt> después de cada escritura a <tt>/dev/fifo</tt>. 
<br>
¿Cómo afecta esto a lo que ve el módulo del kernel?

</p><p>
Para terminar usar la función <tt><a href="http://www.hmug.org/man/2/gettimeofday.php">gettimeofday()</a></tt> para medir el tiempo total de ejecución.
<br>
¿Cómo cambia éste si sacamos la llamada a la función <tt>fflush()</tt>?

</p><p>
En ambos casos para mitigar el "ruido" que cada ejecución pueda tener
(caches internas "frías", inicio de un proceso grande, entrada a una
página muy cargada, etc.), para cada tamaño, repetir el experimento
unas <i>K=100</i> veces, mirar el promedio y/o los últimos valores.

<!--............................................................-->
</p><h3>¿Qué es lo que está pasando?</h3>

<p>
¿Por qué el tamaño del paquete importa?
<br>
¿En qué caso se debe usar <tt>fflush</tt> y cuando no es conveniente?


<!--============================================================-->
</p><h1>Qué se debe Entregar</h1>
<ol>
	<li>El dispositivo <tt>fifo</tt>, con su documentación correspondiente.
		<br> (seguir todas las recomendaciones de documentacion, estilo de código y programación dadas hasta el momento)
	</li>
	<li>Informe y códigos de testeo de los experimentos sobre los mecanismos de buffering de la <tt>libc</tt>.</li>
	<!--<%12.14%>Informe con los experimentos y conclusiones sobre latencia del kernel.</li> -->
</ol>


<!--============================================================-->
<h1>Ayudas</h1>
<ul>
	<li>Cometer un error y que el device driver se clave implica reiniciar la máquina. Un ciclo de programación del estilo <i>prueba-error</i> es tortuoso. Se recomienda programar sencillo y bien.</li>
	<li>En espacio de kernel las herramientas de <i>debugging</i> son muy limitadas, asi que hay que programar utilizando el <a href="http://es.wikipedia.org/wiki/Principio_KISS">KISS principle</a>.</li>
	<li>En lenguaje C, el operador de desplazamiento de bits <tt>&gt;&gt;</tt> es muy útil para hacer <i>2<sup>n</sup></i>.</li>
	<li>Utilizar la macro <code>BUG_ON / ASSERT</code> para marcar puntos donde puede haber un bug y el kernel se debe detener.</li>
	<li>Puede ser conveniente instalar una <i>máquina virtual</i>
donde correr un linux sobre linux, asi no se pierde tanto tiempo
reiniciando una máquina física. Algunas posibilidades son: uml, lguest,
kvm, xen, qemu, vmware_player, etc.</li>
</ul>


<!--
<%15.22%>
<h1>Tareas Adicionales</h1>

Si les sobra tiempo pueden hacer las siguientes mejoras:
<ul>
	<li> ... algo, ideas? ...
	</li>
</ul>
-->

<!-- Footer -->
<div align="right"> <br>
	<font size="-1">
	$Date: 2007-10-05 11:56:54 -0300 (Fri, 05 Oct 2007) $,
	$Revision: 116 $
	</font>
</div>


</body></html>